Fault diagnosis is the most widely used approach to help localize physical defects in a failing LSI circuit. In fault diagnosis, a fault model in an abstract circuit model (usually a gate-level netlist) is used to represent the logical behavior of physical defects in an actual LSI circuit. A fault is considered responsible if the simulated response of the fault in the circuit model matches the observed response of the failing circuit under certain criteria used in a fault diagnosis procedure. The locations of physical defects are then identified with the assist of the information on such responsible faults. Clearly, a good fault model and a good diagnosis procedure are needed in order to obtain sufficient resolution in fault diagnosis.
A good fault model for fault diagnosis needs to closely resemble underlying physical defects from two attributes: location and logical behavior. In a gate-level circuit model, the first attribute means one or more nets or pins, and the second attribute means one or more logic values. Fault modeling defines these attributes in a general manner. On the other hand, physical defects can be characterized from three aspects: complexity (simple or complex), temporality (static or dynamic), and cardinality (single or multiple), as described below. A simple defect forces logic value of a single defect position to fix 0 or 1. On the other hand, a complex defect, like a resistive short or open defect, causes a plurality of possible influences around a defect position. A static defect shows the same behavior for all the input vectors, while a dynamic defect shows different behaviors for different input vectors. There may be a single or multiple defects in a circuit.
The defect complexity issue has been addressed by using a set of simple fault models or by using a realistic fault model. For example, there is a case in which four fault models are used to cover various defects. On the other hand, various realistic fault models, such as stuck-open, bridging, transistor leakage, and Byzantine, better reflect actual defect mechanisms. In general, an indirect approach suffers from insufficient diagnosis accuracy and a direct approach suffers from increasing its fault simulation cost.
Recently, the inventor proposed a new realistic fault model, called the X-fault model, for modeling complex defects, especially those with unpredictable and nondeterministic logic behavior (Non-Patent Document 1, 2, Patent Document 1). The X-fault model represents all possible faulty logic behavior of a physical defect or defects in a gate and/or on its fanout branches by using different X symbols assigned onto the fanout branches. This makes the X-fault model highly accurate since no defect information is lost in fault modeling. In addition, partial symbolic fault simulation, instead of full symbolic fault simulation, is used in X-fault simulation in order to achieve high efficiency in terms of computing time. Since an ever-increasing physical defects in deep-submicron LSI circuits manifest themselves by unpredictable and non-deterministic logic behavior, using the X-fault model in fault diagnosis is becoming more and more advantageous.
Per-test fault diagnosis is gaining popularity as an effective approach to handle the cardinality and temporality issues of complex defects. The basic idea is to process failing test vectors separately, one at a time, in fault diagnosis, based on the observation that only one of the multiple defects in an LSI circuit may be activated by one failing test vector in some cases. This allows a single fault model to be assumed for the activated defect and a relatively easy fault diagnosis procedure based on single fault simulation to be used for multiple and/or dynamic defects. That is, per-test fault diagnosis is effective to solve both of the cardinality problem and temporality problem simultaneously.
Several per-test fault diagnosis methods have already been proposed. The single stuck-at fault model, and a combination of stuck-at, stuck-open, net, and bridging faults are used. These methods attempt to find a minimal set of faults that explains as many failing vectors as possible. Such a fault set is called a multiplet. In addition, some method calculates a score for a fault depending on the number of failing vectors explained by the fault, and another method further extracts diagnostic information from multiplets, while yet another method scores each multiplet based on probability functions.
Recently, a per-test fault diagnosis method based on the X-fault model has been proposed. On top of the accuracy achieved by X-fault modeling, this fault diagnosis procedure employs a flexible matching criterion that takes matching details into consideration. The detailed diagnostic information extracted from the relation between an observed response and a simulated response is expressed as a diagnosis value for each X-fault and each failing test vector, and all diagnosis values form a diagnosis table, from which multiplets are obtained and ordered. It has been shown that such per-test X-fault diagnosis can achieve high diagnostic resolution for complex, multiple, and/or dynamic defects.
The following is the specific explanation of the conventional per-test fault diagnosis method, which is also shown in Patent Document 1.
Firstly, the conventional X-fault model is defined as follows.
Definition 1: A fanout gate has one X-fault, corresponding to any physical defect or defects in the gate or on its n fanout branches. The X-fault assumes n different X symbols on the n fanout branches to represent all possible faulty logic values in fault simulation.
FIG. 6 shows the X-fault for an AND gate with two fanout branches.
X1 and X2 denote two arbitrary faulty logic values. Clearly, <X1, X2> represents any possible faulty logic combination that may appear on the fanout branches. Note that the conventional X-fault model treats all fanout branches as directly connected signal lines, without considering that vias may exist at fanout branches.
X-fault simulation is explained in the following. Given an X-fault f and an input vector v, X-fault simulation is to obtain the simulated response of f under v, denoted by SimRes(f, v)={R1, R2, . . . , Rk}, where R1, R2, . . . , Rk (k≧1) are logic combinations at primary outputs, corresponding to k possible faulty logic combinations, C1, C2, . . . , Ck, at the site of f, respectively. Generally, X-fault simulation uses a partial-symbolic procedure, consisting of three steps. That is, (1) X-injection for assigning different X symbols to the fanout branches of a gate, (2) X-propagation for propagating X symbols to primary outputs, and (3) X-resolution for resolving all X symbols at primary outputs to obtain a final simulation result.
FIG. 7. explains X-injection, X-propagation, and X-resolution.
In FIG. 7 (A), X-injection assigns 3 initial X symbols, X1(b1), X2(b2), and X3(b3), to the fanout branches, b1, b2, and b3 of the gate G1, respectively. In FIG. 7 (B), X-propagation is conducted by keeping inversion information but ignoring all other logic functions. For example, the output of the gate G4 is the AND function of X1 (b1) and X2(b2). This functional information is ignored and the result is a new X symbol X4(b1, b2), in which (b1, b2) is used to indicate that the output of G4 only comes from branches b1 and b2. In FIG. 7 (C), X-resolution is conducted to remove the ambiguity due to X symbols existing in the initial simulated response. Since b3 is not responsible, only three possible faulty logic combinations, C1, C2, and C3, need to be considered at the fault site. As a result, the final simulated responses is SimRes(f, v)={R1, R2, R3}, where R1, R2, and R3 correspond to C1, C2, and C3, respectively. Note that in the conventional X-fault simulation procedure, C1, C2, and C3 are assumed to be equivalent, i.e. each of them has an occurrence probability of 25%.
Diagnosis value calculation will be explained in the following. The failing vector v, the simulated response SimRes(f, v)={R1, R2, . . . , Rk} needs to be compared with the observed response ObvRes(v) to extract diagnostic information. The comparison result is represented by a so-called diagnosis value under v and f, denoted by d(f, v), and the conventional method to calculate d(f, v) is as follows.
                              d          ⁡                      (                          f              ,              v              ,              Ri                        )                          =                                            Level              ⁢                                                          ⁢                              (                f                )                                      Lmax                    ×                                                                                    Error_PO                  ⁢                                      (                    v                    )                                                  ⋂                                  Reach_PO                  ⁢                                      (                    f                    )                                                                                                                                  Reach_PO                ⁢                                  (                  f                  )                                                                                                      Formula        ⁢                                  ⁢        1            if Ri is the same as ObvRes(v) on Reach_PO(f); otherwise, d(f, v, Ri)=0. And,
      d    ⁡          (              f        ,        v            )        =            (                        ∑                      i            =            1                    k                ⁢                  d          ⁡                      (                          f              ,              v              ,              Ri                        )                              )        /    k  
Here, Error_PO(v) is the set of all primary outputs on which an observed response has errors, and Reach_PO(f) is the set of primary outputs that is reachable from the gate with the X-fault f. In FIG. 7 (C), Error_PO(v)={PO1} and Reach_PO(f)={PO1, PO2, PO3}. Moreover, Level(f) is the level of the output of the gate with the X-fault f, and Lmax is the maximum level in the circuit, assuming that all primary outputs have level 1. In FIG. 7, Level(f)=3 and Lmax=3.
For the X-fault simulation result shown in FIG. 7 (C), SimRes(f, v)={R1, R2, R3}={<111>, <001>, <001>}, ObvRes(v)=<001>, and the fault-free simulation result is <101>. Clearly, d(f, v, R1)=0 and d(f, v, R2)=d(f, v, R3)=(3/3)□. (1/3)=0.33. Therefore, d(f, v)=(0+0.33+0.33)/3=0.22.
Diagnosis values are calculated for all failing test vectors and faults, and they are stored in a table called a fault diagnosis table, as illustrated in Table 1. Clearly, compared with a normal fault dictionary with only 0 and 1 entries, a fault diagnosis table contains more diagnostic information. It is obvious that diagnosis values are calculated with unique matching criteria, which take the reachable range of primary outputs, the number of matched errors, and the depth of a fault into consideration.
TABLE 1f1f2f3f4f5v10.810.65000v2000.610.170v30.2600.8300v400000.55ave0.270.160.360.040.14
Non-Patent Document 1: X. Wen, T. Miyoshi, S. Kajiihara, L.-T. Wang, K. K. Saluja, and K. Kinoshita, “On Per-Test Fault Diagnosis Using the X-Fault Model”, Proc. Int'l Conf. on Computer-Aided Design, pp. 633-640, 2004.
Non-Patent Document 2: X. Wen, H. Tamamoto, K. K. Saluja, and K. Kinoshita, “Fault Diagnosis for Physical Defects of Unknown Behaviors”, Proc. Asian Test Symp., pp. 236-241, 2003.
Patent Document 1: Japanese Unexamined Patent Application Publication No. 2006-118903